package leetcode;

import java.util.Arrays;

public class MinSubArrayLen {
    public static void main(String[] args) {
//        int[] nums = {1,1,1,1,1,1,1,1};
//        int k = 11;
        int[] nums = {2,3,1,2,4,3};
        int k = 7;
        System.out.println(minSubArrayLen(k, nums));
    }

    /**
     * 前缀和思路
     * 先求出满足的子数组，再设定一个最小数组，根据数组长度求解
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLenTimeOut(int target, int[] nums) {
        int len = nums.length;
        int minLen = Integer.MAX_VALUE;
        for (int start = 0; start < len; start++) {
            int sum = 0;
            for (int end = start; end >= 0; end--) {
                sum += nums[end];
                if (sum >= target) {
                    minLen = Math.min(minLen, start - end + 1);
                    break;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int sumTarget = target + sums[i - 1];
            int bound = Arrays.binarySearch(sums, sumTarget);
            System.out.println(bound);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;

    }
}
